import java.util.*;

class Solution {
    int[] dx={0,0,1,-1};
    int[] dy={1,-1,0,0};
    boolean[][] fn;
    int n;
    int m;

    public int maxAreaOfIsland(int[][] grid) {
        n=grid.length;
        m=grid[0].length;
        fn=new boolean[n][m];
        int max=0;
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(grid[i][j]==1&&!fn[i][j]){
                    int sum=bf(grid,i,j);
                    max=Math.max(max,sum);
                }
            }
        }
        return max;
    }
    public int bf(int[][] grid,int x,int y){
        Queue<int[]> q=new LinkedList<>();
        q.add(new int[]{x,y});
        fn[x][y]=true;
        int sum=0;
        while(!q.isEmpty()){
            int[] ret=q.poll();
            sum++;
            for(int k=0;k<4;k++){
                x=ret[0]+dx[k];
                y=ret[1]+dy[k];
                if(x>=0&&x<n&&y<m&&y>=0&&grid[x][y]==1&&!fn[x][y]){
                    q.add(new int[]{x,y});
                    fn[x][y]=true;
                }
            }
        }
        return sum;
    }
    public int minMutation(String startGene, String endGene, String[] bank) {
        Set<String> hash=new HashSet<>();
//        h是否遍历过
        Set<String> h=new HashSet<>();
        for(int i=0;i<bank.length;i++){
            hash.add(bank[i]);
        }
        if(startGene.equals(endGene)) return 0;
        if(!hash.contains(endGene)) return -1;
        char[] ret={'A','C','G','T'};
        Queue<String> q=new LinkedList<>();
        int count=0;
        q.add(startGene);
        h.add(startGene);
        while(!q.isEmpty()){
            count++;
            int size=q.size();
            while(size-->0){
               char[] gene=q.poll().toCharArray();
//                String gene=q.poll();
                for(int i=0;i<8;i++){
                    for(int j=0;j<4;j++){
                       char[] temp=gene;
//                        char[] temp=gene.toCharArray();
                        temp[i]=ret[j];
                        String str=new String(temp);

                        if(!h.contains(str)&&hash.contains(str)){
                            if(str.equals(endGene)) return count;
                            q.add(str);
                            h.add(str);
                        }
                    }
                }
            }

        }
        return -1;

    }
}
class Solution11 {
    List<String> list;
    public List<String> letterCasePermutation(String s) {
        list=new ArrayList<>();
        StringBuffer ret=new StringBuffer();
        df(s,ret,0);
        return list;
    }
    public void df(String s, StringBuffer ret,int pos){
        if(pos==s.length()){
            list.add(ret.toString());
        }
        for(int i=pos;i<s.length();i++){

            StringBuffer sb=new StringBuffer(ret);
            if('0'<=s.charAt(i)&&s.charAt(i)<='9') {
                sb.append(s.charAt(i));
            }else{
                    df(s,sb.append(s.charAt(i)),i);
                    df(s,sb.append(s.charAt(i)-32),i);
            }
        }


    }
}
class Solution111 {
    public int numDistinct(String s, String t) {
        StringBuffer sb=new StringBuffer();
        return df(s,t,sb,0);

    }
    public int df(String s,String t,StringBuffer sb,int pos){
        int count=0;
        if(sb.length()==t.length()){
            if(sb.toString().equals(t)){
                // System.out.print(sb.toString()+" ");
                return 1;
            }
            return 0;
        }
        for(int i=pos;i<s.length();i++){
            StringBuffer sb1=new StringBuffer(sb);
            sb1.append(s.charAt(i));
            count+=df(s,t,sb1,i+1);
        }
        return count;
    }
}
public class Main {
    public static void main(String[] args) {
        List<Integer> list=new ArrayList<>();
        list.add(1);
        list.add(2);
        Collections.sort(list,(a,b)->b-a);
        list.r
        int[] nums={3,4,2};
        Arrays.sort(nums);
        int n=nums[nums.length-1];
        int[] arr=new int[n+1];
        int k=1;
        for(int i=1;i<nums.length;){
            while(i<nums.length&&nums[i]==nums[i-1]){
                k++;
                i++;
            }
            arr[nums[i-1]]=k*nums[i-1];
            k=1;
            i++;
        }
        arr[n]=n*k;
        int[] f=new int[n+1];
        int[] g=new int[n+1];
        f[0]=arr[0];
        g[0]=0;
        for(int i=1;i<=n;i++){
            g[i]=Math.max(f[i-1],g[i-1]);
            f[i]=g[i-1]+arr[i];
        }
        System.out.println(Math.max(f[n],g[n]));
    }
    public static void main22(String[] args) {
        int[][] matrix={{2,1,3},{6,5,4},{7,8,9}};
        int[][] grid={{1,3,1},{1,5,1},{4,2,1}};
       
        int n=matrix.length;
        int m=matrix[0].length;
        int[][] arr=new int[n+1][m+1];
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                arr[i][j]=Math.min(arr[i-1][j],arr[i][j-1])+grid[i-1][j-1];
            }
        }
        System.out.println(arr[n][m]);
//        int[][] arr = new int[n + 1][m + 2];
//        for (int i = 1; i <= n; i++) {
//            arr[i][0] = arr[i][m + 1] = Integer.MAX_VALUE;
//        }
//
//        for (int j = 1; j <=n; j++) {
//            for (int i = 1; i < m + 1; i++) {
//                arr[j][i] = Math.min(arr[j - 1][i- 1], Math.min(arr[j - 1][i], arr[j - 1][i + 1])) + matrix[j - 1][i - 1];
//            }
//        }
//
//        int min= Integer.MAX_VALUE;
//        for (int i = 1; i < m + 1; i++) {
//            if(arr[n][i]<min){
//                min=arr[n][i];
//            }
//        }
//        System.out.println(min);

//        Solution11 S=new Solution11();
//        String s = "a1b2";
//       List<String> RET= S.letterCasePermutation(s);
//        System.out.println(RET);


    }
    public static void main1(String[] args) {
        String gene="AAAAACCC";
        String geneend="AACCCCCC";
        String[] bank={"AAAACCCC","AAACCCCC","AACCCCCC"};
        Solution solution=new Solution();
      int a=  solution.minMutation(gene,geneend,bank);
        System.out.println(a);
    }

    public static void main2(String[] args) {
        Set<String> set=new HashSet<>();
        Solution s=new Solution();
        int[][] grid=new int[][]{{0,1,1,0},{1,1,1,1},{1,1,1,1},{0,0,0,0},{0,1,1,1}};
        System.out.println(s.maxAreaOfIsland(grid));
    }
    public static void main11(String[] args) throws Exception{
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int m = in.nextInt();
        int xs = in.nextInt();
        int ys = in.nextInt();
        int xt = in.nextInt();
        int yt = in.nextInt();
        int[] dx = {0, 0, 1, -1};
        int[] dy = {-1, 1, 0, 0};
        boolean[][] fn = new boolean[n + 1][m + 1];
        char[][] arr = new char[n + 1][m + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                arr[i][j] = in.next().charAt(0);
            }
        }
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] {xs, ys});
        fn[xs][ys] = true;
        int  count = 0;
        while (!q.isEmpty()) {
            if(fn[xt][yt]) break;

            int size = q.size();
            count++;
            while (size-- > 0) {

                int[] ret = q.poll();
                for (int i = 0; i < 4; i++) {
                    int x = ret[0] + dx[i];
                    int y = ret[1] + dy[i];

                    if (x < n +1&& x > 0 && y > 0 && y <= m && arr[x][y] == '.' && !fn[x][y]) {
                        q.add(new int[] {x, y});
                        fn[x][y] = true;
                    }
                }

            }
        }
        if (fn[xt][yt]) System.out.println(count);
        else System.out.println(-1);

    }

}